package com.yun.algorithmproblem.leetcodenotcomplete;

import java.util.Arrays;
import java.util.HashSet;

/**
 * 3291. 形成目标字符串需要的最少字符串数 I
 * <p>
 * 给你一个字符串数组 words 和一个字符串 target。
 * <p>
 * 如果字符串 x 是 words 中 任意 字符串的
 * 前缀
 * ，则认为 x 是一个 有效 字符串。
 * <p>
 * 现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。
 */

public class Leetcode3291 {

    public static void main(String[] args) {
        Leetcode3291 obj = new Leetcode3291();
        String[] words = new String[]{"babccdecceddbdaddcddcacedb"};
        String target = "b";
        int ans = obj.minValidStrings(words, target);
        System.out.println(ans);
    }

    public int minValidStrings(String[] words, String target) {
        HashSet<String> hashSet = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        int maxString = 0;
        int tLength = target.length();
        char[] targetCharArray = target.toCharArray();
        int[] maxJump = new int[tLength + 1];
        for (int i = 0; i < tLength; i++) {
            sb.setLength(0);
            for (int j = i; j < tLength; j++) {
                sb.append(targetCharArray[j]);
                if (sb.length() > maxString) {
                    maxString = sb.length();
                    for (String word : words) {
                        if (word.length() >= maxString) {
                            hashSet.add(word.substring(0, maxString));
                        }
                    }
                }
                if (!hashSet.contains(String.valueOf(sb))) {
                    maxJump[i] = sb.length() - 1;
                    break;
                }
                if (j == tLength - 1) {
                    maxJump[i] = sb.length();
                }
            }
        }
        System.out.println(Arrays.toString(maxJump));
        return jump(maxJump);
    }

    public int jump(int[] nums) {
        int ans = 0;
        int curRight = 0;
        int nextRight = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (i == nextRight && nums[i] == 0) {
                return -1;
            }
            nextRight = Math.max(nextRight, i + nums[i]);
            if (i == curRight) {
                curRight = nextRight;
                ans++;
            }
        }
        return ans;
    }
}
